package com.desheng.bigdata.ds.link;

/**
 * @Description 快慢指针解决中间值的问题
 *      就是说一个链表中，通过有两个指针，一个指针移动的速度快，另外一个移动的速度慢，
 *      通常快指针移动的速度是慢指针的2倍，所以一个显而易见的结果就是，当快指针走到了
 *      链表的末尾，慢指针就刚刚走到链表的中间位置。
 * @Author deshenglijun
 * @Date 2020/5/12 21:41
 * @Version 1.0
 */
public class FastAndSlowPointer2MidValue {
    public static void main(String[] args) {
        Node<String>[] nodes = new Node[10];
        for(int i = 0; i < nodes.length; i++) {
            nodes[i] = new Node<String>(null, i + "" + i);
        }
        //组成一个链表
        for(int i = 0; i < nodes.length - 1;) {
            nodes[i].next = nodes[++i];
        }
        // 0 1 2 3 4 5 6 7 8 9
        // 0 2 4 6 8
        // 0 1 2 3 4

        String mid = getMid(nodes[0]);
        System.out.println("mid: " + mid);
    }

    /**
     * 通过快慢指针来获取链表的中间值
     * @param node
     * @return
     */
    private static <E> E getMid(Node<E> node) {
        Node<E> fast = node;
        Node<E> slow = node;
        while(fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow.data;
    }


    static class Node<E> {
        E data;
        Node<E> next;

        public Node(Node<E> next, E data) {
            this.data = data;
            this.next = next;
        }
    }
}
